package com.ttx.algorithm.leetcode.traversal;

import java.util.LinkedList;
import java.util.Queue;

/**
 * https://leetcode-cn.com/problems/number-of-islands/
 * 200 岛屿数量  <br>
 *
 * <p>
 *     给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。
 *     一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。
 *     你可以假设网格的四个边均被水包围。
 *
 *    输入:
 *    11000
 *    11000
 *    00100
 *    00011
 *
 *    输出: 3
 *
 * </p>
 *
 * @author TimFruit
 * @date 19-10-1 下午11:12
 */
public class P200NumberOfIslands2 {

    public int numIslands(char[][] grid) {

        if(grid==null || grid.length==0){
            return 0;
        }
        int rows=grid.length;
        int len=grid[0].length;

        int num=0;//岛屿个数


        for(int i=0;i<rows;i++){
            for(int j=0;j<len;j++){


                if(grid[i][j]=='0'){
                    continue;
                }

                // grid[i][j]== '1', 发现新岛屿
                num++;
                //遍历标记新岛屿
                markIsland(grid,  i, j, rows, len);

            }


        }



        return num;
    }


    //dfs优化
    private void markIsland(char[][] grid, int i, int j, int rows, int len){

        grid[i][j]='0';


        //上
        if(i-1>=0 && grid[i-1][j]=='1' ){
            markIsland(grid, i-1, j , rows, len);
        }

        //下
        if(i+1<rows && grid[i+1][j]=='1' ){
            markIsland(grid, i+1, j , rows, len);
        }

        //左
        if(j-1>=0 && grid[i][j-1]=='1'){
            markIsland(grid, i, j-1 , rows, len);
        }

        //右
        if(j+1<len && grid[i][j+1]=='1' ){
            markIsland(grid, i, j+1 , rows, len);
        }



    }






}
